package com.jn.algorithm.day002.question5;

/**
 * 求字符串的回文子串
 *
 * @author 江南大学1033190417
 * @date 2022/4/16 16:09
 */
public class Solution {

    //暴力解法
    public String longestPalindrome(String s) {
        String bestResult = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                String str = s.substring(i, j);
                if (str.length() > bestResult.length() && isPalindrome(str)) {
                    bestResult = str;
                }
            }
            String str = s.substring(i);
            if (str.length() > bestResult.length() && isPalindrome(str)) {
                bestResult = str;
            }
        }
        return bestResult;
    }

    public boolean isPalindrome(String s) {
        int length = s.length();
        for (int i = 0; i < length / 2; i++) {
            char c1 = s.charAt(i);
            char c2 = s.charAt(length - i - 1);
            if (c1 != c2) {
                return false;
            }
        }
        return true;
    }

    //动态规划
    public String longestPalindrome2(String s) {
        int len = s.length();
        if (len == 1) {
            return s;
        }

        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        int maxLength = 1;
        int begin = 0;
        char[] chars = s.toCharArray();
        //枚举子串长度长度
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                //由L，i确定右边界
                //j-i+1=L
                int j = L + i - 1;
                if (j >= len)
                    break;
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {//如果子串=2，那么一定是回文子串
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {//如果Si-Sj是回文子串，则保存位置和长度
                    begin = i;
                    maxLength = L;
                }
            }
        }
        return s.substring(begin, begin + maxLength);
    }




    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "babad";
        System.out.println(solution.longestPalindrome2(s));

    }
}
